This invention relates generally to two-dimensional barcodes, and, more particularly, to a spread-spectrum barcode that allows the barcode to be read in its entirety even if a significant fraction or majority of the barcode is obscured.
The visual storage of information has been widely deployed in the form of one-dimensional barcodes. Within the past decade, two-dimensional barcodes have emerged to facilitate the dense storage of data. Both one- and two-dimensional barcodes require a registration procedure, normally called xe2x80x9cclockingxe2x80x9d in the barcode literature, to be able to interpret the visual information. To date, a variety of clocking methods have been patented and put to use. See, for example U.S. Pat. No. 5,091,966 to Bloomberg et al., U.S. Pat. Nos. 5,862,270 and 6,115,508 to Lopresti et al., U.S. Pat. No. 6,082,619 to Ma et al., U.S. Pat. No. 4,948,955 to Lee et al., U.S. Pat. No. 5,974,200 to Zhou et al., U.S. Pat. No. 5,521,368 to Adachi, U.S. Pat. No. 5,835,639 to Honsinger et al., and U.S. Pat. No. 4,435,835 to Sakow et al. The methods currently in use rely upon fiducial marks (including blank space), placed at discrete locations within the image, to determine the position and arrangement of the barcode. If these fiduciaries are obscured, the user data within the barcode may not be recoverable. Furthermore, the user data are encoded in discrete locations within the barcode so that when any portion of the barcode image is obscured user data may be lost. This is the case even when error-correction and data redundancy are employed.
As discussed above, numerous techniques for visually encoding user data have been devised and patented. See, for example, U.S. Pat. No. 5,128,525 to Stems et al., U.S. Pat. No. 5,940,135 to Petrovic et al., and U.S. Pat. Nos. 5,862,270 and 6,115,508 to Lopresti et al. Many of the known techniques utilize two-dimensional formats. Commonly known formats include, xe2x80x9cAztec Code,xe2x80x9d xe2x80x9cData Matrix,xe2x80x9d xe2x80x9cData Strip Code,xe2x80x9d xe2x80x9cMaxiCode,xe2x80x9d xe2x80x9cPDF 417,xe2x80x9d xe2x80x9cMicro-PDF 417,xe2x80x9d and xe2x80x9cQR Code.xe2x80x9d Each of these conventional formats localizes data in characters or xe2x80x9cglyphsxe2x80x9d that are designed to facilitate machine reading. As mentioned previously, if part of the barcode is damaged or obscured, some or all of the user data may be lost. There is, therefore, a need for a method to visually encode user data so that it is not affected by damage to the barcode.
The present invention relates to a novel barcode methodology in which the user data is delocalized or distributed across the barcode image. The resulting spread-spectrum barcode may be read in its entirety even if a significant fraction or majority of the barcode is obscured. The present invention also relates to a novel barcode methodology in which the fiducial data is delocalized or distributed across the barcode image. These delocalized fiduciaries are used to register or xe2x80x9cclockxe2x80x9d the data, facilitating the reading of barcodes applied on curved or warped surfaces from images having significant amounts of rotation, magnification, and perspective. In the new registration methodology, the barcode reader recognizes two signature characteristics of the barcode image: a signature xe2x80x9ctexturexe2x80x9d and a signature xe2x80x9cpattern.xe2x80x9d These signatures are known by the barcode reader and are present regardless of the contents of user data sets within the barcode. This registration information allows the barcode image to be corrected for imaging distortions such as zoom, rotation, tilt, curvature, and perspective.
It is therefore an object of the invention to provide a method of recording information on a printed medium that will allow for retrieval of the recorded data even when significant percentage of the recorded data, i.e., greater than approximately 50% and up to approximately 80% of the recording data, is obscured.
It is an additional object of the invention to provide a method of recording information on a printed medium that will allow for accurate retrieval of the recorded data even when topography of the printed recording has been altered by bending, warping, rotation, zooming, etc.
It is another object of the invention to provide a method of recording multiple data sets on a single printed medium wherein the individual data sets may be selectively retrieved.
It is a further object of the invention to provide a method of recording information on a printed medium that can be accurately registered and retrieved without the need of a border or null space.
Additional objects, advantages, and novel features of the invention will be set forth in part in the description that follows, and in part, will become apparent to those skilled in the art upon examination of the following, or may be learned by practice of the invention.
One aspect of the invention is a novel method of recording and visually retrieving user data in a format similar to a conventional two-dimensional barcode. Unlike conventional barcodes, however, user data is spread across the barcode so that the all data can be retrieved even if a significant fraction or majority, i.e., in excess of approximately 50% and up to approximately 80%, of the image is occluded or obscured.
Various methods are available for distributing user data, generally represented as an array of bits, across an image. In one method, each bit individually or in groups is redundantly permuted and repeated at a large number of locations distributed throughout an array of values that will describe the barcode image. The barcode image is then formed, e.g., by printing the image array using a monochrome, grayscale, or color look-up table to transform the values of the image array to pixel tones. The sequence of locations of the bits and the nature of the permutation at each repetition must be known by the reader to recover the user data from the barcode image.
The permutations and location sequences can be generated algorithmically and pseudo-randomly. The locations of bits within the array can be unique, i.e., no two bits are encoded at the same array location, or non-unique, i.e., bits can be superimposed. Multiple data sets can be superimposed on the same image using different location and permutation sequences. Each data set can only be recovered if the precise location and permutation sequences are known. By crafting the permutation and location sequence algorithm, the barcode can be given a signature texture that is substantially independent of the data that is encoded. Moreover, a known pattern of bits can be interspersed, pre-appended, or appended to the user data to provide a signature pattern. The utilities of these signatures will be described later. The data-modulation methodology is analogous to xe2x80x9cfrequency hoppingxe2x80x9d data transception in spread-spectrum wireless communications.
In one methodology for forming the barcode that is analogous to xe2x80x9cdirect-sequencexe2x80x9d spread-spectrum data transception, the barcode is produced by first encoding the user data into a spatial representation, referred to herein as an xe2x80x9cencoded user data array,xe2x80x9d and then modulating this encoded user data array into a modulated data array image using a pseudo-random carrier called a xe2x80x9cmodulating kernel.xe2x80x9d The modulated data array is then formatted and printed onto a printing medium as a barcode. As in conventional spread-spectrum optical encoding and serial communications, multiple data sets can be multiplexed without interference on the same data channel (barcode image) by the use of uncorrelated modulation kernels. See for example, Yamazaki et al. (2001), xe2x80x9cOptimization of encrypted holograms in optical security systems,xe2x80x9d Opt. Eng. 40(1):132-137; Refregier et al. (1995), xe2x80x9cOptical image encryption based on input plane and Fourier plane random encoding,xe2x80x9d Opt. Lett. 90:767-769; Javidi, B. (1997), xe2x80x9cSecuring information with optical technologies,xe2x80x9d Phys. Today 50:27-32; Yang et al. (1996), xe2x80x9cPractical image encryption scheme by real-valued data,xe2x80x9d Opt. Eng. 35:2473-2478; Javidi et al. (1996), xe2x80x9cExperimental demonstration of the random phase encoding technique for image encryption and security verification,xe2x80x9d Opt. Eng. 35:2506-2512; Unnikrishnan et al. (2000), xe2x80x9cDouble random fractional Fourier-domain encoding for optical security,xe2x80x9d Opt. Eng. 39:2853-2859; and Nomura et al. (2000), xe2x80x9cOptical encryption using a joint transform correlator architecture,xe2x80x9d Opt. Eng. 39:2031-2035. The modulated data may only be recovered using the demodulating kernel that is related to the specific modulating kernel that was used to modulate the data set. Thus, multiple sets of user data may be multiplexed onto a single barcode image using uncorrelated modulating and demodulating kernels, allowing secure, covert, individualized, and/or hierarchical access to the user data sets. The user data is recovered from a barcode image by first demodulating the barcode to obtain the encoded data array, and then decoding this array.
This storage and retrieval method is greatly facilitated by the precise registration of the barcode image and the encoding kernel. In one embodiment of the method of the invention, registration is facilitated by simultaneously distributing two types of fiducial information across the barcode image. The first type of distributed fiduciary is a signature texture. This signature texture is recognized by the barcode reader, which infers from distortions in the signature texture an initial estimate of a transform that can map the scanned barcode image into a coarsely corrected image that is free of rotation, tilt, perspective, curvature, and warp. The transform will generally not be derived and applied to the entire barcode at one time, but rather, will be focused on discrete subimages (subsets of the entire image) with each subset being corrected in sequence. While the signature texture provides information regarding rotation, tilt, etc, of each subimage, it does not provide information regarding the physical translation of the individual subimages or resolve a 180-degree rotation ambiguity.
The second type of distributed fiduciary is a signature pseudo-random or deterministic image pattern signature that the barcode reader locates in each of the coarsely corrected subimages. The signature pattern provides translational registration and resolves the rotation ambiguity, thereby completing coarse image registration. Moreover, this signature pattern can be used to enhance the registration accuracy via processing analogous to a two-dimensional phase-locked loop.
Techniques for producing the signature texture include superimposing a xe2x80x9ctexture carrierxe2x80x9d image having the desired texture onto the data-bearing barcode image and crafting the spatial encoding of the user data so that the data-bearing barcode image texture substantially matches a signature texture regardless of the actual data. Similarly, techniques for producing the signature pattern include superimposing a xe2x80x9cpattern carrierxe2x80x9d image having the desired pattern onto the data-bearing barcode image and crafting the encoding of the user data so that the data-bearing barcode image pattern substantially matches a signature pattern regardless of the actual user data.
Any combination of the above signature-producing techniques may be employed to facilitate barcode reading. The superimposition of fiducial data onto the data bearing barcode provides a robust way of ensuring a texture or pattern is present and the same superimposed image can function as the texture and the pattern carrier. While the superimposition technique allows for virtually any data-encoding scheme to be used, it may limit user-data capacity, as there is an additive loss in capacity when images are superimposed on the data-bearing barcode.
The crafting of the data-encoding scheme to produce a texture or pattern has the advantage of not significantly affecting user data capacity, but may be affected by the type of user data encoded. For example, a crafted encoding scheme that produces the desired texture when random user data are encoded may fail when highly ordered data are encoded, e.g., a long string of repeated characters. Fortunately, the problems inherent in either technique can be identified when the user data are encoded and appropriate measures taken. Methods of modifying the user data to improve the characteristics of the encoded data include, for example, compressing the user data to improve data capacity or appending or interspersing non-user data to remove repetitive data sequences.